﻿#pragma once
#include "Index.h"

/**
 * 复杂链表的复制.
 * https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/description/
 *
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），
 * 请对此链表进行深拷贝，并返回拷贝后的头结点。
 */
namespace RandomListClone
{
	struct Node
	{
		int val;
		struct Node *next, *random;
		Node(int x)
			:val(x), next(NULL), random(NULL)
		{
		}

		std::string ToString() const
		{
			std::string node_str=StringUtil::Format("[val:%d random:%d]",val,random?random->val:-1) ;
			if(next)
				node_str+="->"+next->ToString();
			return node_str;
		}
	};

	class Question
	{
	public:
		virtual Node* copyRandomList(Node* head)=0;
	};

	class HashMapSolution:public Question
	{
	public:
		Node* copyRandomList(Node* head) override
		{
			if (head == nullptr)
				return head;

			std::unordered_map<Node*, Node*> clonedNodes;

			//遍历链表，创建出链表结点
			Node* node = head;
			while (node != nullptr)
			{
				clonedNodes[node] = new Node(node->val);
				node = node->next;
			}

			//遍历链表，建立链表结点链接
			node = head;
			while (node != nullptr)
			{
				Node* clonedNode = clonedNodes[node];
				if (clonedNode != nullptr)
				{
					if (node->next != nullptr)
						clonedNode->next = clonedNodes[node->next];
					if (node->random != nullptr)
						clonedNode->random = clonedNodes[node->random];
				}
				node = node->next;
			}
			//返回深拷贝后的链表头
			return clonedNodes[head];
		}
	};

	class InplaceCloneSolution:public Question
	{
	public:
		Node* copyRandomList(Node* head) override
		{
			if(!head)
				return nullptr;

			//每个链表节点的next指向克隆的新节点
			Node* node=head;
			while(node)
			{
				Node* next=node->next;

				Node* clone_node=new Node(node->val);
				node->next=clone_node;
				clone_node->next=next;
				node=next;
			}

			//建立random连接
			node=head;
			while(node)
			{
				if(node->random)
				{
					Node* clone_node=node->next;
					clone_node->random=node->random->next;
				}
				node=node->next->next;
			}

			//建立next连接
			Node* clone_head=head->next;
			node=head;
			while(node)
			{
				Node* clone_node=node->next;
				Node* node_next=clone_node->next;
				if(node_next)
				{
					clone_node->next=node_next->next;
				}

				//为了不对原先链表产生破坏,移除克隆链表节点
				node->next=node_next;
				node=node_next;
			}

			return clone_head;
		}
	};

	class Practice:public Question
	{
	public:
		Node* copyRandomList(Node* head) override
		{
			if(!head)
				return nullptr;

			//旧链表节点到克隆的新链表节点映射
			std::map<Node*,Node*> nodes_map;

			//创建出克隆链表节点
			Node* node=head;
			while(node)
			{
				Node* clone_node=new Node(node->val);
				nodes_map[node]=clone_node;
				node=node->next;
			}

			//克隆链表建立连接关系
			node=head;
			while(node)
			{
				Node* clone_node=nodes_map[node];

				if(node->next)
					clone_node->next=nodes_map[node->next];
				if(node->random)
					clone_node->random=nodes_map[node->random];

				node=node->next;
			}

			return nodes_map[head];
		}
	};


	TEST(TestRandomListClone,CommonCase)
	{
		//创建出复杂链表
		constexpr int LIST_NODE_COUNT=53;
		std::map<int,Node*> list_nodes_map;
		std::set<Node*> list_nodes_set;
		for(int i=0;i<LIST_NODE_COUNT;++i)
		{
			auto node= new Node(i);
			list_nodes_map[i]=node;
			list_nodes_set.emplace(node);
		}

		//建立链表的next连接
		for(int i=0;i<LIST_NODE_COUNT-1;++i)
		{
			list_nodes_map[i]->next=list_nodes_map[i+1];
		}

		//建立链表的random连接
		for (auto kvp : list_nodes_map)
		{
			Node* node=kvp.second;
			//30%为null
			if(!TestingUtil::randPercentage(0.3f))
			{
				const int random_to_index= TestingUtil::randIntBetween(0,LIST_NODE_COUNT-1);
				node->random=list_nodes_map[random_to_index];
			}
		}

		TEST_SOLUTION3(Question,HashMapSolution,InplaceCloneSolution,Practice, &)
		{
			auto input_list=list_nodes_map[0];
			auto cloned_list= solution->copyRandomList(input_list);

			EXPECT_EQ(input_list==nullptr,cloned_list==nullptr);

			Node* cloned_node=cloned_list;
			//克隆的全部节点检查
			std::map<int,Node*> cloned_nodes_map;
			while(cloned_node)
			{
				//深度拷贝中不应出现原先链表中的节点
				EXPECT_TRUE(list_nodes_set.count(cloned_node)<=0);
				cloned_nodes_map[cloned_node->val]=cloned_node;
				cloned_node=cloned_node->next;
				//防止出现死循环
				if(cloned_nodes_map.size()>LIST_NODE_COUNT)
					break;
			}
			EXPECT_EQ(cloned_nodes_map.size(),LIST_NODE_COUNT);

			Node* node=input_list;
			cloned_node=cloned_list;
			while(node)
			{
				EXPECT_TRUE(cloned_node!=nullptr);
				EXPECT_EQ(cloned_node->val,node->val);

				if(node->random)
				{
					EXPECT_TRUE(cloned_node->random!=nullptr);
					EXPECT_EQ(cloned_node->random->val,node->random->val);
					EXPECT_EQ(cloned_node->random,cloned_nodes_map[node->random->val]);
				}
				node=node->next;
				cloned_node=cloned_node->next;
			}
			EXPECT_EQ(node==nullptr,cloned_node==nullptr);
		};
	}
}
